﻿using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Grafos;

namespace GrafosTestUnit {
    /// <summary>
    /// Testes na classe Grafo
    /// </summary>
    [TestClass]
    public class TesteGrafo {

        /// <summary>
        /// Testa a consistência dos nomes dos vértices (sem repetição)
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria um grafo G
        /// Adiciona o vértice "V1" a G
        /// Tenta adicionar o vértice "V1" a G, causando uma DuplicateNameException
        /// </remarks>
        [TestMethod]
        [ExpectedException(typeof(DuplicateNameException))]
        public void DuplicidadeNomeVértice() {
            Grafo g;

            g = new Grafo();
            g.AdicionarVértice("V1");
            g.AdicionarVértice("V1");
        }

        /// <summary>
        /// Verifica se duas arestas são paralelas corretamente
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria o grafo G
        /// Cria três vértices V1, V2, V3
        /// Cria três arestas A=(V1, V2), B=(V2, V3), C=(V1, V2)
        /// Adiciona-se os vértices a G
        /// Adiciona-se as arestas a G
        /// Verifica-se:
        /// G possui aresta paralela a A
        /// G possui aresta paralela a (V2-V3)
        /// G possui aresta paralela a (V1-V3)
        /// G não possui aresta paralela a B
        /// </remarks>
        [TestMethod]
        public void ArestasParalelas() {
            Grafo g;
            Vértice v1, v2, v3;
            Aresta a1, a2, a3;

            v1 = new Vértice("G1");
            v2 = new Vértice("G2");
            v3 = new Vértice("G3");

            a1 = new Aresta(v1, v2);
            a2 = new Aresta(v2, v3);
            a3 = new Aresta(v1, v2);

            g = new Grafo();

            g.AdicionarVértice(v1);
            g.AdicionarVértice(v2);
            g.AdicionarVértice(v3);

            g.AdicionarAresta(a1);
            g.AdicionarAresta(a2);
            g.AdicionarAresta(v1, v3);

            Assert.IsTrue(g.PossuiArestaParalela(a1)); // a1 paralela a a3
            Assert.IsTrue(g.PossuiArestaParalela(v2, v3)); // a2 é paralela a v2-v3
            Assert.IsTrue(g.PossuiArestaParalela(v1, v3)); // aresta adicionada manualmente v1-v3

            Assert.IsFalse(g.PossuiArestaParalela(a2)); // nenhuma aresta fora a2 é paralela a a2
        }

        /// <summary>
        /// Testa se a detecção de ciclos está correta
        /// </summary>
        /// <remarks>
        /// Cria um grafo G com três vértices V1, V2, V3
        /// Verifica-se que G não possui ciclo
        /// Adiciona (V1, V2) a G
        /// Verifica-se que G não possui ciclo
        /// Adiciona (V1, V3) a G
        /// Verifica-se que G não possui ciclo
        /// Adiciona (V2, V3) a G
        /// Verifica-se que G possui ciclo
        /// Limpa as arestas de G
        /// Adiciona (V1, V2), (V1, V3) e (V1, V1) a G
        /// Verifica-se que G possui ciclo
        /// Limpa as arestas de G
        /// Adiciona (V1, V2) e (V1, V1) a G
        /// Verifica-se que G possui ciclo
        /// </remarks>
        [TestMethod]
        public void PossuiCiclos() {
            Grafo g;
            Vértice v1, v2, v3;

            v1 = new Vértice("G4");
            v2 = new Vértice("G5");
            v3 = new Vértice("G6");

            g = new Grafo();

            g.AdicionarVértice(v1);
            g.AdicionarVértice(v2);
            g.AdicionarVértice(v3);

            Assert.IsFalse(g.PossuiCiclo());

            g.AdicionarAresta(v1, v2);
            Assert.IsFalse(g.PossuiCiclo());

            g.AdicionarAresta(v1, v3);
            Assert.IsFalse(g.PossuiCiclo());

            g.AdicionarAresta(v2, v3);
            Assert.IsTrue(g.PossuiCiclo());

            v1 = new Vértice("G7");
            v2 = new Vértice("G8");
            v3 = new Vértice("G9");
            g = new Grafo();
            g.AdicionarVértice(v1);
            g.AdicionarVértice(v2);
            g.AdicionarVértice(v3);
            g.AdicionarAresta(v1, v2);
            g.AdicionarAresta(v1, v3);
            g.AdicionarAresta(v1, v1);
            Assert.IsTrue(g.PossuiCiclo());

            v1 = new Vértice("G10");
            v2 = new Vértice("G11");
            g = new Grafo();
            g.AdicionarVértice(v1);
            g.AdicionarVértice(v2);
            g.AdicionarAresta(v1, v2);
            g.AdicionarAresta(v1, v1);
            Assert.IsTrue(g.PossuiCiclo());
        }

        /// <summary>
        /// Valida a busca em largura do grafo
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria o grafo G, com vértices A..J e arestas A-B, A-D, B-C, C-D, C-E, E-F, E-G, E-H, F-G, H-I, H-J, I-J
        /// Realiza a busca em largura em G, partindo do vértice A, gravando o resultado na árvore ARV
        /// Verifica-se:
        /// ARV possui 9 arestas
        /// ARV possui 10 vértices
        /// O grafo G possuia ciclos
        /// ARV possui as arestas A-B, A-D, C-E, E-F, E-G, E-H, H-I, H-J
        /// ARV possui ou a aresta B-C ou D-C, mas não ambas
        /// </remarks>
        [TestMethod]
        public void BuscaEmLargura() {
            Grafo g, r;
            Árvore a;
            bool ciclo;

            g = new Grafo();
            g.AdicionarVértice("A", "B", "C", "D", "E", "F", "G", "H", "I", "J");
            g.AdicionarAresta(
                new Tuple<string, string>("A", "B"),
                new Tuple<string, string>("A", "D"),
                new Tuple<string, string>("B", "C"),
                new Tuple<string, string>("C", "D"),
                new Tuple<string, string>("C", "E"),
                new Tuple<string, string>("E", "F"),
                new Tuple<string, string>("E", "G"),
                new Tuple<string, string>("E", "H"),
                new Tuple<string, string>("F", "G"),
                new Tuple<string, string>("H", "I"),
                new Tuple<string, string>("H", "J"),
                new Tuple<string, string>("I", "J"));

            a = g.BuscaEmLargura(g.BuscarVértice("A"), out r, out ciclo);

            Assert.AreEqual(9, a.QuantidadeArestas);
            Assert.AreEqual(10, a.QuantidadeVértices);
            Assert.IsTrue(ciclo);
            Assert.IsTrue(a.PossuiArestaParalela("A", "B"));
            Assert.IsTrue(a.PossuiArestaParalela("A", "D"));
            Assert.IsTrue(a.PossuiArestaParalela("B", "C") ^ a.PossuiArestaParalela("D", "C"));
            Assert.IsTrue(a.PossuiArestaParalela("C", "E"));
            Assert.IsTrue(a.PossuiArestaParalela("E", "F"));
            Assert.IsTrue(a.PossuiArestaParalela("E", "G"));
            Assert.IsTrue(a.PossuiArestaParalela("E", "H"));
            Assert.IsTrue(a.PossuiArestaParalela("H", "I"));
            Assert.IsTrue(a.PossuiArestaParalela("H", "J"));
        }

        /// <summary>
        /// Verifica se a busca em largura identifica a falta de ciclos corretamente
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria o grafo G com vértices A, B e C, e arestas A-B e B-C
        /// Realiza uma busca em largura em G
        /// Verifica-se que:
        /// A árvore gerada possui 2 arestas
        /// A árvore gerada possui 3 vértices
        /// G não possuia ciclos
        /// </remarks>
        [TestMethod]
        public void BuscaEmLarguraSemCiclo() {
            Grafo g, r;
            Árvore a;
            bool ciclo;

            g = new Grafo();
            g.AdicionarVértice("A", "B", "C");
            g.AdicionarAresta(
                new Tuple<string, string>("A", "B"),
                new Tuple<string, string>("B", "C"));

            a = g.BuscaEmLargura(g.BuscarVértice("A"), out r, out ciclo);

            Assert.AreEqual(2, a.QuantidadeArestas);
            Assert.AreEqual(3, a.QuantidadeVértices);
            Assert.IsFalse(ciclo);
        }

        /// <summary>
        /// Testa o resto de uma busca em largura aplicada a um grafo desconexo
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria um grafo G, com vértices A..J, e vértices A-B, A-D, B-C, C-D, E-F, E-G, E-H, F-G, H-I, H-J, I-J
        /// Realiza uma busca em largura em G, gravando a árvore resultando em ARV e o resto em R
        /// Verifica-se:
        /// ARV possui 3 arestas
        /// ARV possui 4 vértices
        /// G possuia ciclos
        /// ARV possui as arestas A-B e A-D
        /// ARV possui ou B-C ou D-C, mas não ambas
        /// R possui 7 arestas
        /// R possui 6 vértices
        /// </remarks>
        [TestMethod]
        public void BuscaEmLarguraComResto() {
            Grafo g, r;
            Árvore a;
            bool ciclo;

            g = new Grafo();
            g.AdicionarVértice("A", "B", "C", "D", "E", "F", "G", "H", "I", "J");
            g.AdicionarAresta(
                new Tuple<string, string>("A", "B"),
                new Tuple<string, string>("A", "D"),
                new Tuple<string, string>("B", "C"),
                new Tuple<string, string>("C", "D"),
                new Tuple<string, string>("E", "F"),
                new Tuple<string, string>("E", "G"),
                new Tuple<string, string>("E", "H"),
                new Tuple<string, string>("F", "G"),
                new Tuple<string, string>("H", "I"),
                new Tuple<string, string>("H", "J"),
                new Tuple<string, string>("I", "J"));

            a = g.BuscaEmLargura(g.BuscarVértice("A"), out r, out ciclo);

            Assert.AreEqual(3, a.QuantidadeArestas);
            Assert.AreEqual(4, a.QuantidadeVértices);
            Assert.IsTrue(ciclo);
            Assert.IsTrue(a.PossuiArestaParalela("A", "B"));
            Assert.IsTrue(a.PossuiArestaParalela("A", "D"));
            Assert.IsTrue(a.PossuiArestaParalela("B", "C") ^ a.PossuiArestaParalela("D", "C"));

            Assert.AreEqual(7, r.QuantidadeArestas);
            Assert.AreEqual(6, r.QuantidadeVértices);
        }


        /// <summary>
        /// Verifica se o grafo calcula os componentes conexos corretamente
        /// </summary>
        /// <remarks>
        /// Cria um grafo G1 com vértices V1..V4
        /// Define os grafos G2 e G3 como cópias de G1
        /// Adiciona em G1 (V1, V2), (V2, V3), (V3, V4)
        /// Adiciona em G2 (V1, V2), (V3, V4)
        /// Nenhuma aresta é adiciona a G3
        /// Verifica-se:
        /// G1 possui 1 componente conexo
        /// G2 possui 2 componentes conexos
        /// G3 possui 4 componentes conexos
        /// </remarks>
        [TestMethod]
        public void CálculoComponentesConexos() {
            Grafo g, g2, g3;
            Vértice v1, v2, v3, v4;

            v1 = new Vértice("V1");
            v2 = new Vértice("V2");
            v3 = new Vértice("V3");
            v4 = new Vértice("V4");

            g = new Grafo();
            g.AdicionarVértice(v1);
            g.AdicionarVértice(v2);
            g.AdicionarVértice(v3);
            g.AdicionarVértice(v4);

            g2 = g.Cópia();
            g3 = g.Cópia();

            g.AdicionarAresta(v1, v2);
            g.AdicionarAresta(v2, v3);
            g.AdicionarAresta(v3, v4);

            v1 = g2.BuscarVértice("V1");
            v2 = g2.BuscarVértice("V2");
            v3 = g2.BuscarVértice("V3");
            v4 = g2.BuscarVértice("V4");

            g2.AdicionarAresta(v1, v2);
            g2.AdicionarAresta(v3, v4);

            Assert.AreEqual(1, g.ComponentesConexos());
            Assert.AreEqual(2, g2.ComponentesConexos());
            Assert.AreEqual(4, g3.ComponentesConexos());
        }

        /// <summary>
        /// Verifica se o grafo Kn gerado está correto
        /// </summary>
        /// <remarks>
        /// Cria um grafo g com vértices V1, V2, V3 e V4
        /// São adicionadas a g as arestas V1-V2, V1-V3, V1-V1, V2-V4, V1-V2
        /// Gera-se o grafo kn a partir de g
        /// Verifica-se:
        /// kn possui 4 vértices
        /// kn possui 6 arestas
        /// </remarks>
        [TestMethod]
        public void GerarKn() {
            Grafo g, kn;

            g = new Grafo();

            g.AdicionarVértice("V1", "V2", "V3", "V4");
            g.AdicionarAresta("V1", "V2");
            g.AdicionarAresta("V1", "V3");
            g.AdicionarAresta("V1", "V1");
            g.AdicionarAresta("V2", "V4");
            g.AdicionarAresta("V2", "V1");

            kn = g.GerarKN();

            Assert.AreEqual(4, kn.QuantidadeVértices);
            Assert.AreEqual(6, kn.QuantidadeArestas);
        }
    }
}
